package org.raymond.iworks.study.basic.structure.tree;

import org.raymond.iworks.study.basic.algorithm.sort.SelectSortTest;

import java.util.Arrays;

/**
 * 堆排序基本介绍
 * 1) 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,
 * 平均时间复杂度均为O(nlogn),它也是不稳定排序.
 * 2) 堆是具有以下性质的完全二叉树:每个节点的值都大于或等于其左右孩子节点的值.称为大顶堆,
 * 注意:没有要求节点的左孩子的值和右孩子的值的大小关系.
 * 3) 每个节点的值都小于或等于其左右孩子节点的值,称为小顶堆.
 * 4) 大顶堆:
 *                     50(0)
 *           45(1)               40(2)
 *      20(3)     25(4)     35(5)     30(6)
 * 10(7)     15(8)
 * 对堆中的节点按层进行编号,得到数组:{50,45,40,20,25,35,30,10,15}
 * 大顶堆的特点: arr[i]>=arr[2*i+1] && arr[i]>=arr[2*i+2]
 * 注:i对应第几个节点,从0开始编号
 *
 * 5) 小顶堆:
 *                     10(0)
 *           20(1)               15(2)
 *      25(3)     50(4)     30(5)     40(6)
 * 35(7)     45(8)
 * 对堆中的节点按层进行编号,得到数组:{10,20,15,25,50,30,40,35,45}
 * 小顶堆的特点: arr[i]<=arr[2*i+1] && arr[i]<=arr[2*i+2]
 * 注:i对应第几个节点,从0开始编号
 *
 * 6) 一般升序采用大顶堆,降序采用小顶堆
 *
 * 堆排序的基本思想:
 * 1) 将待排序序列构造成一个大顶堆(该树以数组的形式存放)
 * 2) 此时,整个序列的最大值就是堆顶的根节点
 * 3) 将其与末尾元素进行交换,此时末尾就是最大值
 * 4) 然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值.如此反复执行,便能得到一个有序序列了.
 *
 * 可以看到在构建大顶堆的过程中,元素的个数逐渐减少,最后就得到一个有序序列了.
 *
 * 要求:给你一个数组[4,6,8,5,9],要求使用堆排序,将数组升序排序.
 * 步骤一 构造初始堆,将给定无序序列构造成一个大顶堆(一般升序用大顶堆，降序用小顶堆)
 * 原始的数组: [4,6,8,5,9]
 * 1) 假设给定的无序序列结构如下:
 *             4(0)
 *     6(1)            8(2)
 * 5(3)    9(4)
 *
 * 2) 此时,我们从最后一个非叶子节点开始(叶节点自然不用调整,第一个非叶子节点
 * arr.length/2-1=5/2-1=1, 也就是下面的6节点),从左至右,从下至上进行调整.
 *             4(0)                               4(0)
 *     6(1)            8(2)    ===>>>     9(1)            8(2)
 * 5(3)    9(4)                       5(3)    6(4)
 * 调整后的数组: [4,9,8,5,6]
 * 注: [6,5,9]中9最大,于是9与6交换(大顶堆,父大于子,因此9应该放在父节点位置上)
 *
 * 3) 同理,找到第二个非叶子节点4,由于[4,9,8]中9最大,4和9交换
 *             4(0)                               9(0)
 *     9(1)            8(2)    ===>>>     4(1)            8(2)
 * 5(3)    6(4)                       5(3)    6(4)
 *
 * 4) 交换后,子树[4,5,6]不满足大顶堆,继续调整,[4,5,6]中6最大,交换4和6
 *             9(0)                               9(0)
 *     4(1)            8(2)    ===>>>     6(1)            8(2)
 * 5(3)    6(4)                       5(3)    4(4)
 * 调整后的数组: [9,6,8,5,4]
 *
 * 5) 8(2)不是非叶子节点,不用调整
 *
 * 此时,我们将一个无序序列构造成了一个大顶堆
 *
 * 步骤二 将堆顶元素与末尾元素进行交换,使末尾元素最大.然后继续调整堆,再将堆顶元素与末尾元素交换,
 * 得到第二大元素.如此反复进行交换,重建...交换,重建
 * 1) 将堆顶元素9和末尾元素4进行交换
 *             9(0)                               4(0)
 *     6(1)            8(2)    ===>>>     6(1)            8(2)
 * 5(3)    4(4)                       5(3)    9(4)
 * 调整后的数组: [4,6,8,5,9]
 *
 * 2) 重新调整结构,使其继续满足堆定义
 * 参考步骤一:从最后一个非叶子节点开始,从左至右,从下至上,将子树的最大元素放置在子树根上
 * 对于[4,6,8,5,9],只计算[4,6,8,5];
 * 子树 5(3)<-6(1) 中6>=5,不用调整;
 * 子树 [4,6,8] 中8最大,4和8交换;
 * 结果如下:
 *             4(0)                               8(0)
 *     6(1)            8(2)    ===>>>     6(1)            4(2)
 * 5(3)    9(4)                       5(3)    9(4)
 * 调整后的数组: [8,6,4,5,9]
 *
 * 3) 再将堆顶元素8与末尾元素5进行交换,得到第二大元素8
 *             8(0)                               5(0)
 *     6(1)            4(2)    ===>>>     6(1)            4(2)
 * 5(3)    9(4)                       8(3)    9(4)
 * 调整后的数组: [5,6,4,8,9]
 *
 * 4) 后续过程,继续进行调整,交换,如此反复 进行,最终使得整个序列有序
 * 4.1) 对于[5,6,4],6最大,交换4和6;
 *             5(0)                               6(0)
 *     6(1)            4(2)    ===>>>     5(1)            4(2)
 * 8(3)    9(4)                       8(3)    9(4)
 * 调整后的数组: [6,5,4,8,9]
 * 4.2) 堆顶的6与末尾的4交换:
 *             6(0)                               4(0)
 *     5(1)            4(2)    ===>>>     5(1)            6(2)
 * 8(3)    9(4)                       8(3)    9(4)
 * 调整后的数组: [4,5,6,8,9]
 * 4.3) 对于[4,5],只有两个数值,按大小交换后再按堆顶堆尾交换无意义;直接得到结果
 * 结果数组: [4,5,6,8,9]
 *
 * 堆排序思路总结:
 * 1) 将无序序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;
 * 2) 将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;
 * 3) 重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,
 * 反复执行调整+交换的步骤,直到整个序列有序.
 */
public class HeapSortDemo {
    public static void main(String[] args) {
        int[] arr = newArr();
        //arr = new int[]{3, 9, -1, 10, -2};
        //arr = new int[]{8,9,1,7,2,3,5,4,6,0};
        //arr = new int[]{4,6,8,5,9, -1,90,89,56,-999};
        //System.out.printf("待排序数组:%s\n", Arrays.toString(arr));
        int[] cloned = Arrays.copyOf(arr, arr.length);
        long start = System.nanoTime();
        heapSort(arr);
        long end = System.nanoTime();
        //System.out.printf("堆排序结果:%s\n", Arrays.toString(arr));
        // post: 19,341,172 纳秒,约19毫秒, 100,000个元素
        // post: 2,316,211,395 纳秒,约2316毫秒, 10,000,000个元素的数组
        System.out.printf("耗时:%d\n", (end-start));

        start = System.nanoTime();
        SelectSortTest.jdkSort(cloned);
        end = System.nanoTime();
        //System.out.printf("排序结果:%s\n", Arrays.toString(arr));
        // post: 42,068,034 纳秒, 约42毫秒, 100,000个元素的数组
        // post: 1,145,566,881 纳秒, 约1145毫秒, 1千万个元素
        System.out.printf("jdksort 耗时:%d\n", (end-start));
    }
    public static void heapSort(int[] arr){
        int temp = 0;
        // 1) 将无序序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆
        for(int i=arr.length/2-1; i>=0; i--){
            adjustHeap(arr, i, arr.length);
        }
        /**
         * 2) 将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;
         * 3) 重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,
         * 反复执行调整+交换的步骤,直到整个序列有序.
         */
        for(int j=arr.length-1; j>0; j--){
            // 交换
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            // 重新调整结构
            adjustHeap(arr,0,j);
        }
    }

    /**
     * 将以非叶子节点为根的树(二叉树)调整为大顶堆
     * 举例:{4,6,8,5,9} =>
     * i=1, adjustHeap=>{4,9,8,5,6}
     * i=0, adjustHeap=>{9,4,8,5,6}
     * i=1, adjustHeap=>{9,6,8,5,4}
     * 满足大顶堆,交换堆顶与末尾
     * swap{4,6,8,5,9}
     * @param arr 待调整的数组
     * @param i 非叶子节点索引
     * @param length 待调整的元素个数,逐渐减少
     */
    public static void adjustHeap(int[] arr, int i, int length){
        int temp=arr[i];
        // 大顶堆,设i为当前节点,i的左子节点为i*2+1,即k
        // 因此这里k为i的左子节点,下一轮(k=k*2+1)是继续找k的左子节点
        for(int k=i*2+1; k<length; k=k*2+1){
            // k+1<length 防止k++后arr[k]越界
            // arr[k]<arr[k+1] 判断左子节点的值是否小于右子节点的值,为满足大顶堆做准备
            if(k+1<length && arr[k]<arr[k+1]){
                k++; // 如果小于,则k指向右子节点,即拿到较大值的数组下标
            }
            // 如果较大子节点大于父节点,则不符合大顶堆定义,需要交换
            if(arr[k]>temp){
                // 把较大的值赋给当前节点
                arr[i]=arr[k];
                // i指向k,即将位置i指向原来较大值的位置,继续循环比较
                i=k;
            }else{
                // 注意调整的顺序是从左至右,从下至上
                // 所以这里不用担心子树的结构,因为输入的i就要配合保证调整的顺序
                break;
            }
        }
        // 当for循环结束后,我们已经将以i为根的树的最大值,放在了i处

        // 现在i已经指向了原来较大值的位置,现在将temp值放到这个位置上,完成堆内结构的调整
        // 即完成父节点较小值和左右子节点较大值的交换
        arr[i] = temp;
    }


    public static int[] newArr(){
        int[] arr = new int[10_000_000];
        for(int i=0; i<arr.length; i++){
            arr[i]=(int)(Math.random()*Integer.MAX_VALUE);
        }
        return arr;
    }
}
